#-*- coding: utf-8 -*-

import time
import sys

from random import uniform
from time import clock
'''

 autor: António Delgado
 Data: 11-03-2013


'''

'''ordernar elementos do array'''
class Bubblesort:
    def __init__(self, A):
        self.A = A
    
    def Bubblesort(self, A):
        for i in range(0, len(self.A) -1):
            for j in range(len(self.A)-1, i, -1 ):
                if self.A[j] < self.A[j-1]:
                    self.A[j], self.A[j-1] = self.A[j-1], self.A[j]
                    
        return A
  
    
A=[3, 1, 2, 4, 7, 6, 5, 10, 9, 8]
execucaoOne= time.clock()
print 'Desordenado:', A
g = Bubblesort(A)
execucaoTwo= time.clock()
print 'Ordenado:', g.Bubblesort(A)
print 'Time Inicial:', execucaoOne
print 'Time final:', execucaoTwo
print 'Time Final-Inicial:', execucaoTwo-execucaoOne

Z = [1] + range(50, 1050, 50)
T = []
M = 25
for n in Z:
    A = [ uniform(0.0,1.0) for k in xrange(n)]
    tempos = []
    for k in range(M):
        t1 = clock()
        Bubblesort(A)
        t2 = clock()
        tempos.append(t2-t1)
    media = reduce(lambda x, y: x + y, tempos) / len(tempos)
    var = reduce(lambda x, y: x + (y-media)**2, [0] + tempos) / len(tempos)
    
    T.append((n,media, var))

X = [n for n, media, var in T]
Y = [media for n, media, var in T]
ct=15e6
Z = [n**2/ct for n, media, var in T]

import matplotlib.pyplot as plt
plt.grid(True)
plt.ylabel(u'T(n) - tempo de execução médio em segundos')
plt.xlabel(u'n - número de elementos')
plt.plot(X,Y,'rs', label="resultado experimental")
plt.plot(X, Z, 'b^', label=u"previsão teórica")
plt.legend()
plt.show()
